1. Field of the Invention
The present invention relates generally to the design of integrated circuits (ICs), and more particularly to the routing phase of an IC design.
2. Prior Art
Due to the ever increasing complexity of integrated circuit (IC) designs, IC designers become more and more reliant on electronic design automation (EDA) tools. An IC is fabricated by a series of lithographic steps that may be abstracted as a construction of a multilayered stack of materials, each layer consisting of a large set of simple geometries. In the related art, EDA tools that manipulate modular sets (e.g., component libraries, IP blocks, and so on) of simple geometries are provided. Each such modular set consists of geometries that exist on several or all lithographic layers of the IC and contains a logic function, ranging from a simple inverter library cell to an IP block module that may hold a microprocessor.
Generally, the processing steps taken by an EDA tool to obtain an IC layout are: a) mapping of the logic for an IC to existing blocks and further partitioning the circuit into blocks of modules or circuits; b) floor planning, which finds the alignment and relative orientation of the circuit blocks; c) placement, which determines more precisely the positions of the circuit blocks and their component blocks; d) routing, which completes the interconnects among electrical components; and e) verification, which checks the layout to ensure that it meets design and functional requirements.
Routing is a key operation in the physical design cycle. Routing consists of establishing a set of electrical conductors that may be constructed on almost any of the geometries and most of the lithographic layers. However, due to the ever-increasing electrical constraints, modern ICs bound all routing geometries to metal layers, wherever such layers have not been utilized by the connections within the library modules or IP building blocks. Given the fact that modern technology includes many metal layers, placement procedures construct a complete packing of the building IP modules or blocks with no space reserved for routing. All routing is then constructed from geometries that exist on the layers above the building blocks contents.
A set of terminal points to be connected is commonly known as a net. Geometries that may have been utilized in the construction of the already placed building blocks are represented as a list of obstacles for the routing problem. Routing is usually performed in two phases: global and detailed. In the global routing, the routing of the nets of the circuit disregards the exact geometric details of each wire and terminal. For each wire, a global router finds a topology that represents the wires of a given net. That is, the global routing specifies the loose route of a wire through the routing space, attempting to reconcile net demand on routing space. The global routing is followed by a detailed routing that completes the point-to-point connections, thereby realizing the connectivity of each net. Global routing usually includes detailed information, such as layer assignment of wire segments, widths of wires, and so on. The detailed routing is performed using a fine router.
Due to the fact that a typical IC consists of millions of nets, a routing of a single net is a NP-hard problem. This fact indicates a potential of extremely high demands on computational resources. Therefore, it would be advantageous to provide a solution that simplifies the routing of IC designs and allows routing tasks to be executed by standard computational resources.